1. Field of the Invention
The present invention relates to methods and apparatus for the processing of digital signals.
2. Prior Art
Various architectures of digital signal processing circuitry such as digital filters and the like are well known in the art. Most of these architectures use a conventional binary numbering system to represent the parameters and the signals. Some architectures, though, use a Residue Number System (RNS) to represent both the parameters and the signals. An RNS representation has the advantage that the operations of multiplication, addition and subtraction--the basic operations in filtering, signal detection and the like--are exceedingly fast because, in contrast to a binary numbering system, no carries between digits are necessary to perform the operations. It has been reported in the literature that this speed advantage is the sole advantage of using an RNS system over using a conventional system of numbering.
In an RNS representation of a number X, the number is represented by a number of digits wherein each digit has its own limited range as follows: EQU X=x.sub.ma,x.sub.mb, . . . ,x.sub.mN
where:
X=a natural number
x.sub.ma, x.sub.mb, . . . x.sub.mN are each a digit in the RNS representation of the natural number X wherein:
x.sub.ma =X mod(m.sub.a)=the remainder after X is divided by m.sub.a. The remainder is therefore less than m.sub.a. PA1 x.sub.mb =X mod(m.sub.b), etc., and PA1 m.sub.a, m.sub.b . . . m.sub.N are the different moduli (integer numbers), each associated with a respective digit in the RNS representation of the natural number X. PA1 where: m=the modulus of the digit, a positive integer PA1 1.) X is evenly divisible by the integer divisor d (remainder=0). Then X/d is clearly an integer number, and expressible in RNS form in the same RNS system as X. PA1 2.) The divisor and the modulus of the RNS digit are relatively prime. PA1 where: PA1 N.sub.d =the integer value of (X/d)/m=(N-n)/d PA1 x.sub.d =(x+n*m)/d=the value of the RNS digit in the RNS representation of X/d PA1 x.sub.d can also be found directly by using RNS multiplication of x by a number called the multiplicative inverse of d, as follows: Since (x+n*m)/d=x.sub.d : EQU x+n*m=x.sub.d *d PA1 then EQU x*I.sub.dm mod(m)=xd mod(m)=x.sub.d PA1 I.sub.dm, then, is the multiplicative inverse of d in the modulus m. If d is relatively prime with respect to m the multiplicative inverse exists (without proof herein), hereinafter denoted d.sub.m.sup.-1. PA1 where a.sub.1, a.sub.2, etc. are functions of x.sub.1, x.sub.2, etc. PA1 where x.sub.2 ' is the value of the second RNS digit after the subtraction of a.sub.1 and the division by m.sub.1. PA1 Pos/Neg, M even: -M/2&lt;=X&lt;=M/2-1 PA1 Pos/Neg, M odd: -(M-1)/2&lt;=X&lt;=(M-1)/2
If the moduli are relatively prime, that is, the smallest single number into which all will divide evenly is equal to the product of all the moduli, then the range of numbers that can be uniquely represented in any particular RNS form X=x.sub.ma,x.sub.mb, . . . ,x.sub.mN is m.sub.a *m.sub.b * . . . *m.sub.N. This excludes the possibility of repetition of a modulus, but not even numbers or a perfect square. For instance note that 3, 4 and 5 are relatively prime in that the smallest single number into which all will divide evenly is 60, even though 4 is both an even number and a perfect square.
As an example of the foregoing, consider the example of a Residue Number System shown in Table 1. In this RNS, each integer is represented by three RNS digits x.sub.3, x.sub.5 and x.sub.7, the subscript of each digit being the value of the associated modulus. Thus this is a 3, 5, 7 RNS, being able to distinguish 3*5*7=105 unique integers. As can be seen from Table 1, no RNS representation repeat in the range from 0 to 104, though the entire sequence begins to repeat again if one tries to extend the same to 105 and beyond.
TABLE 1 ______________________________________ Natural RNS RNS RNS Number digit digit digit X x.sub.3 x.sub.5 x.sub.7 ______________________________________ 105 0 0 0 104 2 4 6 . . . . . . . . . . . . 15 0 0 1 14 2 4 0 13 1 3 6 12 0 2 5 11 2 1 4 10 1 0 3 9 0 4 2 8 2 3 1 7 1 2 0 6 0 1 6 5 2 0 5 4 1 4 4 3 0 3 3 2 2 2 2 1 1 1 1 0 0 0 0 ______________________________________
As an example of how the RNS system works, consider the natural number 14. The x.sub.3 digit is 14 mod(3)=the remainder 2, i.e. 14/3=4 remainder 2. The x.sub.5 digit is 14 mod(5)=the remainder 4, i.e. 14/5=2 remainder 4. The x.sub.7 digit is 14 mod(7)=the remainder 0 (14/7=2 remainder 0). It will be noted that each digit is determined without reference to any other digit in the RNS representation.
Also note that the same 3,5,7 RNS representation might be used to uniquely represent the numbers 105 to 209. However addition, subtraction and multiplication of any two numbers in the range of 105 to 209 all provide a result which is out of the range of 105 to 209, making this scheme rather useless for digital signal processing. Of particular interest for digital signal processing however, is the introduction of negative numbers by limiting the range of numbers representable in the RNS system chosen to an equal or substantially equal number of positive and negative numbers, as most signals processed will have or can be made to have a substantially zero average value. Such an assignment for a 3,5,7 RNS system is shown in Table 2. Again note that 105 numbers -52 to +52 are uniquely represented in the RNS, but the representations begin to repeat at 53 and -53. Note also that no separate sign is associated with positive or negative RNS numbers, but instead the sign is determined by the digits themselves once the RNS system and its range is selected. Finally, note that even the sign of the associated natural number represented in RNS form cannot be determined from any less than all the RNS digits in the RNS representation of the number.
TABLE 2 ______________________________________ Natural RNS RNS RNS Number digit digit digit X x.sub.3 x.sub.5 x.sub.7 ______________________________________ 53 2 3 4 52 1 2 3 . . . . . . . . . . . . 15 0 0 1 14 2 4 0 13 1 3 6 12 0 2 5 11 2 1 4 10 1 0 3 9 0 4 2 8 2 3 1 7 1 2 0 6 0 1 6 5 2 0 5 4 1 4 4 3 0 3 3 2 2 2 2 1 1 1 1 0 0 0 0 -1 2 4 6 -2 1 3 5 -3 0 2 4 -4 2 1 3 -5 1 0 2 -6 0 4 1 -7 2 3 0 -8 1 2 6 -9 0 1 5 -10 2 0 4 -11 1 4 3 -12 0 3 2 -13 2 2 1 -14 1 1 0 -15 0 0 6 . . . . . . . . . . . . -52 2 3 4 -53 1 2 3 ______________________________________
For RNS addition, each respective pair of digits of the two RNS numbers are added and the applicable modulo operation is performed on each respective sum.
Example ##EQU1##
But 3 mod(3)=0 and 7 mod(5)=2. Therefore the sum 375 in the RNS system is 025, representing the natural number 12 (see Table 2).
For subtraction, the same procedure is followed, though the modulus may have to be added back to bring the "remainder" into the range of 0 to the respective modulus minus 1.
Example ##EQU2##
But adding the applicable modulus of 7 to -5 gives a "remainder" of 2. Therefore plus 13 subtracted from plus 8 in this RNS system is 102, representing the natural number -5 (see Table 2).
For addition involving a negative number, the same procedure is followed as in addition of positive numbers.
Example ##EQU3##
But 4 mod(3) is 1 and 5 mod(5) is 0. Therefore -13 added to 8 in this RNS system is 102, again representing the natural number -5 (see Table 2).
Finally, in the case of multiplication, consider the following example:
Example ##EQU4##
But 12 mod(7) is 5. Therefore (-3)*(-4) in this RNS system is 025, again representing the natural number 12 (see Table 2).
It can be seen that addition, subtraction and multiplication of positive and negative numbers expressed in a RNS form work in the RNS system. The key observation to be made, though, is that the operations are performed on each RNS digit independently, without reference to results of the same operation on any other RNS digit. The high speed characteristic of RNS arithmetic is due to this "carry free" nature of the operations, whereas in conventional arithmetic, the results of multiplication, addition or subtraction of a particular digit cannot be finally determined until the results of the operation on less significant digits have been determined.
Division is also possible in an RNS system, with certain essential limitations. The principles of division in an RNS system may be illustrated as follows. In a single digit x of an RNS representation of a natural number X: EQU X=m*N+x
N=an integer (which will be a negative integer for negative numbers) PA2 x=the value of the RNS digit (the remainder, in the range of 0.ltoreq.x.ltoreq.m-1, after subtracting m*N from X)
For any individual RNS digit, only x, the value of the digit itself, is known. Knowledge of only a single digit does not give knowledge of X, or N for that digit.
The above equation for X may be written in various ways as follows: ##EQU5## where: n=is an arbitrary positive integer
The operation of division can occur on an RNS digit by RNS digit basis provided the following two conditions are met (the satisfaction of these two conditions will be commented on hereafter on a case by case basis):
Using the above equations for X, X/d may be expressed in a conventional number system by any of the following equations: ##EQU6##
If there is a value of n where (x+n*m)/d is an integer, then because X/d is also an integer, m*(N-n)/d is an integer. Therefore, m*(N-n) must include a factor d. Since it is assumed that m is relatively prime with respect to d, (N-n) must include the factor d, and so (N-n)/d is also an integer.
Furthermore, if for one and only one value of n, (x+n*m)/d is an integer in the range of 0 to m-1, then X/d=m*(N-n)/d+(x+n*m)/d is in the form of the equation: EQU X/d=m*N.sub.d +x.sub.d
If m and d are relatively prime, it is stated without proof will be one and only one value of n for which (x+n integer in the range of 0 to m-1.
By way of example, consider a digit of modulus 5 of an RNS representation of a number X evenly divisible by d. First consider 56 divided by 7=8. The modulus 5 RNS digit x of 56 is 1 and the modulus 5 RNS digit x.sub.d of 8 is 3. Therefore x=1 and x.sub.d should come out out to be 3. Though not known from x, N=the integer value of 56/5=11. The possibilities for x.sub.d =(x+n*m)/d in the range of 0 to 4 for various values of n, and for N.sub.d =(N-n)/d are shown in Table 3 below.
TABLE 3 ______________________________________ X.sub.d (x + n*m) (x + n*m)/d N.sub.d (x + n*m)/d = n (x = 1) (d = 7) (N - n)/d an integer ______________________________________ 0 1 1/7 11/7 1 6 6/7 10/7 2 11 11/7 9/7 3 16 16/7 8/7 4 21 21/7 = 3 7/7 = 1 3 ______________________________________
While the foregoing only illustrates the division of 56 by 7, the second and third columns of Table 3 are the same for any number X evenly divisible by 7 and having an RNS digit of modulus 5 equal to 1. Thus in any RNS system in which one of the RNS digits has a modulus of 5, when that RNS digit has a value of 1 in the RNS representation of a number X evenly divisible by 7, the corresponding digit in the RNS representation of the result of dividing X by 7 will always be 3. The same procedure may be used to find the respective value of the RNS digit of modulus 5 in X/7 when the corresponding RNS digit in X has any of the other values 0, 2, 3 and 4 (x.sub.d =0, 1, 4 and 2, respectively).
This same technique, of course, can readily be further extended to division in general wherein the divisor and the modulus of the digit are relatively prime and it is known that X/d is an integer. It also works for negative numbers. For instance, consider -49 divided by 7. For -49, an RNS digit of modulus 5 is also 1. Therefore, as before, the RNS digit of modulus 5 in the RNS representation of the result will be 3, which is the RNS digit of modulus 5 in the RNS representation of -7.
Multiplying both sides of the above equation by some integer I.sub.dm : EQU x*I.sub.dm +n*m*I.sub.dm =x.sub.d *d*I.sub.dm
Then taking mod(m) of both sides gives: EQU (x*I.sub.dm +n*m*I.sub.dm)mod(m)=(x.sub.d *d*I.sub.dm)mod(m)
The term n*m*I.sub.dm on the left of the above equation can be dropped since it is an integer multiple of the modulus m, and an additional mod(m) operation can be inserted on the right without changing the result. Thus: EQU x*I.sub.dm mod(m)=[x.sub.d *(d*I.sub.dm mod(m))] mod(m)
If an integer Idm can be found such that EQU d*I.sub.dm mod(m)=1
To find the multiplicative inverse d.sub.m.sup.-1 of d for the modulus m, it is not necessary to search through all integers for the integer d.sub.m.sup.-1 such that: EQU d*d.sub.m.sup.-1 mod(m)=1
If d.sub.m.sup.-1 exists, then it is also true that EQU [d*(d.sub.m.sup.-1 mod(m))] mod(m)=1
Given d mod(m) then, it is only necessary to search from 1 through m-1 to find the inverse of d in the modulus m (the inverse cannot be 0).
Note that if d mod(m)=0, then no multiplicative inverse will be found. Of course, if d mod(m)=0, then d and m are not relatively prime and one of the two conditions for division has not been satisfied.
Thus rather than dividing by a number, such as a number d, one can multiply by d.sub.m.sup.-1, the multiplicative inverse of d. To illustrate a multiplicative inverse, consider division by 13 for a modulo 5 digit of an RNS number. The digit may have values of 0, 1, 2, 3 or 4. Using the first approach to division described to divide by 13, the modulus 5 may be repeatedly added to the RNS digit value until the sum is evenly divisible by 13. In that regard, there will be only one such number evenly divisible by 13 to give a result of 0, 1, 2, 3 or 4, as shown in Table 4 below.
TABLE 4 ______________________________________ x + n*m x.sub.d Value x Value of the of the modulo Value of the Add modulus modulo 5 5 digit modulo 5 5 "n" times digit divided by digit n= plus n*5 13 ______________________________________ 0 0 0 0 1 5 26 2 2 10 52 4 3 2 13 1 4 7 39 3 ______________________________________
However, multiplying the value of the modulo 5 digit times 2 gives an identical result. Thus for the modulo 5 digit, dividing by 13 is identical to multiplying by 2. Using the equation: EQU d.sub.m.sup.-1 *d mod(m)=1 EQU .sub.5.sup.-1 *13 mod(5)=1 EQU or again, 13.sub.5.sup.-1 =2
While the operations of addition, subtraction and multiplication are carry free in an RNS system and hence simple and fast to execute, other operations that are simple and fast in a binary numbering system are cumbersome within an RNS system. For example, truncation in a binary system is simply the dropping of the least significant digits of the number to be truncated. In an RNS system, the digits do not have a relative significance, and therefore truncation is problematic.
Other operations that are difficult in an RNS number system include division, scaling (division by a fixed factor), sign detection, comparison, and dynamic range extension. As these are simple operations in binary, it is in principle possible to convert from an RNS number form to binary, perform the operation on the binary number, and then reconvert to an RNS number form if necessary (comparison and sign detection are results in themselves, and the RNS number or numbers on which they have operated may be preserved in RNS form for later use). However the Associated Mixed Radix (AMR) representation of a number can be found more naturally than the binary representation from the RNS representation.
Like a binary or decimal number, a mixed radix number is expressed by digits that have a relative significance. But unlike binary and decimal numbers, the weight of each digit is not a fixed multiple ("radix") of the weight of the immediately less significant digit.
The radix of a decimal number is 10. The value of the least significant digit ranges from 0 to 9. The next most significant digit, which also varies from 0 to 9, has a weight of 10. The next most significant digit has a weight of 100, 10 times larger than the weight of the previous digit, etc. The radix of a binary number is 2. The value of the least significant binary digit ranges from 0 to 1. The next most significant binary digit, which also varies from 0 to 1, has a weight of 2. The next most significant digit has a weight of 4, 2 times larger than the weight of the previous digit, etc.
The radix of a mixed radix number changes from digit to digit. Considering first only positive numbers, the value of the least significant digit ranges from 0 to p-1. The weight of the next most significant digit is "p". The value of this digit, though, ranges from 0 to q-1, where "q" in general is not equal to "p". The weight of the next digit is "q" times the weight of this digit, namely "p" times "q", and its value can range from 0 to yet 20 a different maximum.
Of interest here is when the radices of a mixed radix representation of an integer X are equal to the moduli m.sub.1, m.sub.2, etc. of the RNS representation of the integer X (hence the "Associated" Mixed Radix representation). The value of the least significant digit ranges from 0 to m.sub.1 -1, where m.sub.1 is one of the RNS moduli. (Note that in the following discussion, the notation style has changed. Subscripts no longer indicate the value of the modulus, but rather merely distinguish between RNS system digits.) The next AMR digit, which has a weight of m.sub.1, ranges from 0 to m.sub.2 -1, etc. The natural number X, then, in AMR form can be expressed as EQU X=a.sub.1 +a.sub.2 *m.sub.1 +a.sub.3 *(m.sub.1 *m.sub.2)+a.sub.4 *(m.sub.1 *m.sub.2 *m.sub.3)+ . . .
where a.sub.1, a.sub.2, etc. are the AMR digit values. Note that the range under the AMR representation is identical to the range of the corresponding RNS representation of a number X. For instance, assume four AMR digits a.sub.1, a.sub.2, a.sub.3 and a.sub.4. Then X can range from zero to: EQU X.sub.max =(m.sub.1 -1)+(m.sub.2 -1)*m.sub.1 +(m.sub.3 -1)(m.sub.1 *m.sub.2)+(m.sub.4 -1)*(m.sub.1 *m.sub.2 *m.sub.3)=m.sub.1 *m.sub.2 *m.sub.3 *m.sub.4 -1
The values for the AMR digits a.sub.1, a.sub.2, etc. can be obtained from the RNS representation of X using the following methodology.
Consider a natural number X having the RNS representation x.sub.1,x.sub.2, . . . ,x.sub.N in the moduli m.sub.1, m.sub.2, . . . , m.sub.N. Again X can be expressed as: EQU X=a.sub.1 +a.sub.2 *m.sub.1 +a.sub.3 *m.sub.1 *m.sub.2 + . . . +a.sub.N *m.sub.1 *m.sub.2 * . . . *m.sub.N-1
By taking modulo m.sub.1 of each side of the above equation: EQU X mod(m.sub.1)=(a.sub.1 +a.sub.2 *m.sub.1 + . . . a.sub.N *m.sub.1 * . . . *m.sub.N-1) mod(m.sub.1)
The left side of the above equation is simply equal to x.sub.1. Note that m.sub.1 is a factor in every term on the right side of the equation except the first, and therefore all terms except the first can be dropped. Therefore: EQU x.sub.1 =a.sub.1 mod(m.sub.1)=a.sub.1
Now subtract a.sub.1 from X using RNS subtraction and divide the result by m.sub.1 using RNS division to obtain the result X' in RNS form. EQU X'=(X-a.sub.1)/m.sub.1 =a.sub.2 +a.sub.3 *m.sub.2 + . . . +a.sub.N *m.sub.2 * . . . *m.sub.N-1
Note that subtracting a.sub.1 from X drives the value of the x.sub.1 digit of the RNS representation of X to zero, meaning that the result X-a.sub.1 is evenly divisible by m.sub.1, so that X' is an integer representable in RNS form. Also note that the divisor m.sub.1 is relatively prime to all of the moduli except itself. Therefore, the two conditions for valid RNS division have been satisfied for all RNS digits except the first. Fortunately, the inability to legitimately divide the first digit is of no consequence, as the possible range of the result is diminished so as to be uniquely expressible by the remaining digits.
Now taking mod(m.sub.2) of X': EQU X' mod(m.sub.2)=(a.sub.2 +a.sub.3 *m.sub.2 + . . . +a.sub.N *m.sub.2 * . . . * m.sub.N-1) mod(m.sub.2)
Consequently: EQU x.sub.2 '=a.sub.2 mod(m.sub.2)=a.sub.2
Repeating the process as required: EQU a.sub.1 =x.sub.1, a.sub.2 =x.sub.2 ', a.sub.3 =x.sub.3 ", etc.
As an example of the foregoing, consider the natural number 41 in the 3,5,7 RNS system of Table 1. The natural number 41 is 216 in RNS. Thus: EQU X=216 RNS EQU x.sub.1 =a.sub.1 =2 EQU X-a.sub.1 =X-2=044 RNS EQU X'=(X-a.sub.1)/3=36 RNS (3.sub.5.sup.-1 =2, 3.sub.7.sup.-1 =5) EQU x.sub.2 '=a.sub.2 =3 EQU X'-3=03 RNS EQU X"=(X'-3)/5=2 RNS=x.sub.3 "=a.sub.3 (5.sub.7.sup.-1 =3)
Thus a.sub.1 =2, a.sub.2 =3 and a.sub.3 =2.
As a check: EQU X=a.sub.1 +a.sub.2 *m.sub.1 +a.sub.3 *m.sub.1 *m.sub.2 EQU X=2+3*3+2*3*5=2+9+30=41
Now consider the Associated Mixed Radix representation of positive and negative numbers in the 3,5,7 RNS system of Table 2, wherein the numbers X range from -52 to +52. Again the AMR representation of a number X is: EQU X=a.sub.1 +a.sub.2 *m.sub.1 +a.sub.3 *m.sub.1 *m.sub.2
The moduli m.sub.1, m.sub.2 and m.sub.3 are necessarily positive, but the values of a.sub.1, a.sub.2 and a.sub.3 are not so limited, though each is limited in range to the range of the respective one of m.sub.1, m.sub.2 and m.sub.3. Thus if: EQU -1.ltoreq.a.sub.1 .ltoreq.+1 EQU -2.ltoreq.a.sub.2 .ltoreq.+2 EQU -3.ltoreq.a.sub.3 .ltoreq.+3
Then X will range from -1+(-2*3)+(-3*3*5)=-52 to +1+(+2*3)+(+3*3*5)=+52, as in Table 2.
As an example of the foregoing, again consider the natural number 41 in the 3,5,7 RNS system of Table 2. The natural number 41 is 216 in RNS. Thus: EQU X=216 RNS EQU x.sub.1 =a.sub.1 mod(3)=2
Given that x.sub.1 =a.sub.1 mod(3)=2 and -1.ltoreq.a.sub.1 .ltoreq.+1, a.sub.1 must be -1. EQU X-a.sub.1 =X-(-1)=216 RNS+111 RNS=020 RNS EQU X'=(X-a.sub.1)/3=40 RNS EQU x.sub.2 '=4=a.sub.2 mod(5) EQU a.sub.2 =-1 (since -2.ltoreq.a.sub.2 .ltoreq.+2) EQU X'-a.sub.2 =X'-(-1)=40 RNS+11 RNS=01 RNS EQU X"=(X'-a.sub.2)/5=3 RNS EQU x.sub.3 '=3=a.sub.3 mod(7)=a.sub.3
Thus a.sub.1 =-1, a.sub.2 =-1 and a.sub.3 =3.
As a check: EQU X=a.sub.1 +a.sub.2 *m.sub.1 +a.sub.3 *m.sub.1 *m.sub.2 EQU X=-1+(-1*3)+3*3*5=-1+(-3)+45=41
In the preceding example including a range of negative numbers, all the moduli were odd (i.e., 3, 5 and 7), and the numbers representable in AMR form ranged from -52 to +52. For another system where the moduli are 2, 5, and 11, a range inclusive of positive and negative numbers could instead be from -55 to +54. More generally, the total range representable in AMR form is equal to M=m1*m2* . . . , the product of the moduli. If only positive numbers ranging from 0 are considered, then 0&lt;=X&lt;=M-1. If inclusive of negative numbers also, there are two possibilities of particular interest. If any one of the moduli is an even number, M will be an even number. Otherwise, M will be an odd number. Two possibilities of range inclusive of both positive and negative numbers can therefore be identified:
The determination of the range of the possible values of the individual AMR digits depends on which of the two possibilities apply. If all moduli are odd, then M is odd and the total range is symmetrical about zero. It is therefore necessary for all the AMR digits to also have ranges symmetric about zero. For all AMR digits "aa" associated with moduli "m", then:
For all AMR digits (M odd): -(m-1)/2&lt;=a&lt;=(m-1)/2 as exemplified above in the 3, 5, 7 system.
If one of the moduli is even and M is therefore even, the range inclusive of both positive and negative numbers is not symmetric about zero and the determination of the range of AMR digit values is more complicated. First, note that there can be only one even modulus. Otherwise, the moduli in the RNS system would not be relatively prime (all even moduli would have a common factor of two). The range of AMR digit values depends on the location, in terms of significance, of the digit associated with the even modulus:
______________________________________ AMR digit associated with -m/2 &lt;= a &lt;= m/2 - 1 the even modulus: AMR digits associated with -(m-1)/2 &lt;= a &lt;= (m-1)/2 odd moduli more significant than the digit associated with the even modulus: AMR digits associated with 0 &lt;= a &lt;= m-1 odd moduli less significant than the digit associated with the even modulus: ______________________________________
To understand this arrangement, note that while the total range with M even is asymmetrical about zero, it is only slightly so, and therefore the most significant digits that can have symmetric ranges need to have such. The even digit needs to have an asymmetric range, and it should be in favor of the negative values but only slightly so. Finally, if the even digit is not the least significant digit, even its slightly asymmetric range will give excessive asymmetry towards negative values in the total range, and the less significant odd digits need to acquire only positive values to compensate.
For example, the 2, 5, 11 RNS system briefly mentioned above could, again, represent the natural numbers from -55 to +54. If the AMR representation is such that the AMR digits, from the most significant to the least significant, are associated with the 11, 2, and 5 moduli respectively, then the digits should have the following ranges: EQU -5&lt;=a3&lt;=+5 EQU -1&lt;=a2&lt;=0 EQU 0&lt;=a1&lt;=+4
As a check, the minimum natural number X representable in AMR form is EQU X.sub.min =0+(-1)*5+(-5)*5*2=0-5-50=-55
and the maximum is EQU X.sub.max= 4+0*5+5*5*2=4+0+50=+54
An AMR representation of a number has various uses, such as to create a new RNS digit for an expanded RNS representation of the number. To create the new RNS digit x.sub.N+1 having modulus m.sub.N+1 : EQU X=a.sub.1 +a.sub.2 *m.sub.1 +a.sub.3 *m.sub.1 *m.sub.2 + . . . +a.sub.N *m.sub.1 *m.sub.2 * . . . *m.sub.N-1 EQU x.sub.N+1 =X mod(m.sub.N+1)=(a.sub.1 + . . . +a.sub.N *m.sub.1 * . . . *m.sub.N-1) mod(m.sub.N+1) EQU x.sub.N+1 =((a.sub.1) mod(m.sub.N+1)+(a.sub.2 *m.sub.1) mod(m.sub.N+1)+ . . . ) mod(m.sub.N+1)
Again as an example, consider the generation of a new RNS digit of modulus 11 for the natural number 41 expressed as the 3,5,7 RNS number 216, first in the all positive RNS representations of Table 1. It has already been determined that a.sub.1 =2, a.sub.2 =3 and a.sub.3 =2. In this case: EQU x.sub.N+1 =((a.sub.1) mod(m.sub.N+1)+(a.sub.2 *m.sub.1) mod(m.sub.N+1)+(a.sub.3 *m.sub.1 *m.sub.2) mod(m.sub.N+1)) mod(m.sub.N+1) EQU x.sub.N+1 =(2 mod(11)+(3*3) mod(11)+(2*3*5) mod(11)) mod(11) EQU x.sub.N+1 =((2)+(9)+(30 mod(11))) mod(11) EQU x.sub.N+1 =(2+9+8) mod(11)=19 mod(11)=8
Obviously this is correct, in that 41 mod(11) is 8. Thus the natural number 41, expressed in a 3,5,7 RNS as 216 RNS, is expressed in a 3,5,7,11 RNS as 2168 RNS. While for the natural number 41 the additional RNS digit is redundant, the range of the natural numbers expressible in the new four digit 3,5,7,11 RNS is eleven times that expressible in the three digit 3,5,7 RNS. Note that it was not necessary to determine the actual value of X=41. x.sub.N+1 was determined solely by the RNS and AMR digits. The foregoing is called "Base Extension".
Now consider the generation of a new RNS digit of modulus 11 for the natural number 41 expressed in the 3,5,7 positive and negative number RNS representations of Table 2. It has already been determined that in the positive and negative number range system, a.sub.1 =-1, a.sub.2 =-1 and a.sub.3 =3. In this case: EQU x.sub.N+1 =((a.sub.1) mod(m.sub.N+1)+(a.sub.2 *m.sub.1) mod(m.sub.N+1)+(a.sub.3 *m.sub.1 *m.sub.2) mod(m.sub.N+1)) mod(m.sub.N+1) EQU x.sub.N+1 =((-1) mod(11)+(-1*3) mod(11)+(3*3*5) mod(11)) mod(11)
Thus: EQU x.sub.N+1 =((10)+(8)+(45) mod(11)) mod(11) EQU x.sub.N+1 =(10+8 +1) mod (11)=19 mod(11)=8
In electronic circuits, various encoding schemes are well known in the representation of digit values. In conventional binary encoding, each digit can be represented by a single signal, or a single "line". A line with a high voltage represents a binary "1". A line with a "low" voltage represents a binary "0". In binary coded decimal, each decimal digit is represented by four lines, and the various voltage levels on the lines determine the value of the decimal digit. Commonly used methods and apparatus for the processing of digital signals use one of these two representations of real numbers, most commonly the binary encoding. Decoding of a digit to a 1 of N form is also common, but not for digital processing, but rather for device addressing and for control purposes.